package main.java.com.amanda.suafa;

import edu.princeton.cs.algs4.MinPQ;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.StdOut;
import main.java.com.amanda.utils.Edge;
import main.java.com.amanda.utils.EdgeWeightedGraph;

import java.util.Scanner;

/**
 * @author amanda
 * @Description 最小生成树的prim算法的延时实现
 */
public class LazyPrimMST {
    private boolean[] marked;   // 最小生成树的顶点
    private Queue<Edge> mst;    // 最小生成树的边
    private MinPQ<Edge> pq;     // 横切边（包括失效的边）
    private double weight;

    public LazyPrimMST(EdgeWeightedGraph G) {
        pq = new MinPQ<>();
        marked = new boolean[G.V()];
        mst = new Queue<>();

        visit(G, 0);
        while (!pq.isEmpty()) {
            Edge e = pq.delMin();   // 从pq中得到权重最小的边
            int v = e.either(), w = e.other(v);
            if (marked[v] && marked[w]) // 跳过失效的边
                continue;
            mst.enqueue(e);          // 边添加到树中
            weight += e.weight();

            if (!marked[v]) {        // 将顶点添加到树中
                visit(G, v);

            }
            if (!marked[w]) {
                visit(G, w);

            }
        }
    }

    private void visit(EdgeWeightedGraph G, int v) {
        // 标记顶点并将所有连接v和未被标记顶点的边加入pq
        marked[v] = true;
        for (Edge e : G.adj(v)) {
            if (!marked[e.other(v)]) {
                pq.insert(e);
            }
        }

    }
    public Iterable<Edge> edges() {
        return mst;
    }
    public double weight() {
        return weight;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        EdgeWeightedGraph G = new EdgeWeightedGraph(scanner);
        LazyPrimMST mst = new LazyPrimMST(G);
        for (Edge e : mst.edges()) {
            StdOut.println(e);
        }
        StdOut.print("最小树权重：");
        StdOut.printf("%.5f\n", mst.weight());
    }
}
/*
8 16
4 5 0.35
4 7 0.37
5 7 0.28
0 7 0.16
1 5 0.32
0 4 0.38
2 3 0.17
1 7 0.19
0 2 0.26
1 2 0.36
1 3 0.29
2 7 0.34
6 2 0.40
3 6 0.52
6 0 0.58
6 4 0.93

0-7 0.16
1-7 0.19
0-2 0.26
2-3 0.17
5-7 0.28
4-5 0.35
6-2 0.40
最小树权重：1.81000
 */
